{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 5, 6, 11, 32, 212, 222]\n",
      "[4, 5, 6, 11, 13, 22, 32, 212, 222]\n",
      "[4, 5, 6, 21, 32, 33, 212, 222, 11222]\n",
      "[2, 11, 32, 54, 123, 143, 212, 222, 226]\n"
     ]
    }
   ],
   "source": [
    "#  1. 归并排序 ( 递归 + 合并)\n",
    "#  时间复杂度 T(N) = 2 * T(N/2) + O(N)  =  O(N*logN)\n",
    "\n",
    "def mergeSort(arr: list[int], start=0, end=None):\n",
    "    if end is None: \n",
    "        end = len(arr)-1\n",
    "    if end == start + 1:\n",
    "        a, b = arr[start], arr[end]\n",
    "        return [a, b] if a<b else [b, a]\n",
    "    if start == end:\n",
    "        return arr[start:start+1]\n",
    "    \n",
    "    def merge(arr1, arr2):\n",
    "        new_arr = []\n",
    "        while arr1 or arr2:\n",
    "            if arr1:\n",
    "                if arr2:\n",
    "                    if arr1[0] > arr2[0]:\n",
    "                        new_arr.append(arr2.pop(0))\n",
    "                    else:\n",
    "                        new_arr.append(arr1.pop(0))\n",
    "                else:\n",
    "                    new_arr.append(arr1.pop(0))\n",
    "            else:\n",
    "                new_arr.append(arr2.pop(0))\n",
    "        return new_arr\n",
    "    mid = ((end-start)>>1) + start\n",
    "    \n",
    "    left = mergeSort(arr, start, mid)\n",
    "    right = mergeSort(arr, mid+1, end)\n",
    "    return merge(left, right)\n",
    "\n",
    "print(mergeSort([2,3,4,5,6,212,222,32,11]))\n",
    "print(mergeSort([22,13,4,5,6,212,222,32,11]))\n",
    "print(mergeSort([21,33,4,5,6,212,222,32,11222]))\n",
    "print(mergeSort([2,123,143,54,226,212,222,32,11]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 5, 6, 11, 32, 212, 222]\n",
      "[4, 5, 6, 11, 13, 22, 32, 212, 222]\n",
      "[4, 5, 6, 21, 32, 33, 212, 222, 11222]\n",
      "[2, 11, 32, 54, 123, 143, 212, 222, 226]\n"
     ]
    }
   ],
   "source": [
    "# 2. 冒泡排序\n",
    "def maopao(arr: list[int]):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1, n):\n",
    "            if arr[i]>arr[j]:\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "    return arr\n",
    "\n",
    "print(maopao([2,3,4,5,6,212,222,32,11]))\n",
    "print(maopao([22,13,4,5,6,212,222,32,11]))\n",
    "print(maopao([21,33,4,5,6,212,222,32,11222]))\n",
    "print(maopao([2,123,143,54,226,212,222,32,11]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3. 选择排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 4. 插入排序"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('opencv')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "b04e532e6ce11d72ca7f2113c964d7a5531c18c5e6d3e97b1c42c6f9a3724305"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
